import os, sys

# 把包的父目录添加到系统搜索路径
BASE_DIR=os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
sys.path.append(BASE_DIR)

from base_data_structures.stack import Stack
from base_data_structures.tree import BinaryTree 

# 树的遍历分为三种方式：
#     前序：跟左右
#     中序：左根右
#     后序： 左右根

# 前序遍历树
def preOrder(tree):
    if tree:
        print(tree.getRootVal())
        preOrder(tree.getLeftChild())
        preOrder(tree.getRightChild())

# 中序遍历树
def inOrder(tree):
    if tree != None:
        inOrder(tree.getLeftChild())
        print(tree.getRootVal())
        inOrder(tree.getRightChild())

# 后续遍历
def postOrder(tree):
    if tree !=None:
        postOrder(tree.getLeftChild())
        postOrder(tree.getRightChild())
        print(tree.getRootVal())

if __name__=='__main__':
    tree = BinaryTree('a')
    tree.insertLeft('b')
    l = tree.getLeftChild()
    # print(l.getRootVal()) # b
    l.insertRight("d")
    l.insertLeft('c')
    tree.insertRight('g')
    r=tree.getRightChild()
    r.insertLeft('e')
    r.insertRight('f')

    # preOrder(tree)
    tree.postOrder()
    # print("-=-------")
    # inOrder(tree)